Search Results

Documents authored by Levi, Amit

Document
DOI: 10.4230/LIPIcs.ITCS.2021.42
Ordered Graph Limits and Their Applications

Authors: Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Yuichi Yoshida

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
The emerging theory of graph limits exhibits an analytic perspective on graphs, showing that many important concepts and tools in graph theory and its applications can be described more naturally (and sometimes proved more easily) in analytic language. We extend the theory of graph limits to the ordered setting, presenting a limit object for dense vertex-ordered graphs, which we call an orderon. As a special case, this yields limit objects for matrices whose rows and columns are ordered, and for dynamic graphs that expand (via vertex insertions) over time. Along the way, we devise an ordered locality-preserving variant of the cut distance between ordered graphs, showing that two graphs are close with respect to this distance if and only if they are similar in terms of their ordered subgraph frequencies. We show that the space of orderons is compact with respect to this distance notion, which is key to a successful analysis of combinatorial objects through their limits. For the proof we combine techniques used in the unordered setting with several new techniques specifically designed to overcome the challenges arising in the ordered setting. We derive several applications of the ordered limit theory in extremal combinatorics, sampling, and property testing in ordered graphs. In particular, we prove a new ordered analogue of the well-known result by Alon and Stav [RS&A'08] on the furthest graph from a hereditary property; this is the first known result of this type in the ordered setting. Unlike the unordered regime, here the Erdős–Rényi random graph 𝐆(n, p) with an ordering over the vertices is not always asymptotically the furthest from the property for some p. However, using our ordered limit theory, we show that random graphs generated by a stochastic block model, where the blocks are consecutive in the vertex ordering, are (approximately) the furthest. Additionally, we describe an alternative analytic proof of the ordered graph removal lemma [Alon et al., FOCS'17].
Cite as

Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Yuichi Yoshida. Ordered Graph Limits and Their Applications. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 42:1-42:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2021.42,
  author =	{Ben-Eliezer, Omri and Fischer, Eldar and Levi, Amit and Yoshida, Yuichi},
  title =	{{Ordered Graph Limits and Their Applications}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{42:1--42:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.42},
  URN =		{urn:nbn:de:0030-drops-135815},
  doi =		{10.4230/LIPIcs.ITCS.2021.42},
  annote =	{Keywords: graph limits, ordered graph, graphon, cut distance, removal lemma}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.80
Erasure-Resilient Sublinear-Time Graph Algorithms

Authors: Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We investigate sublinear-time algorithms that take partially erased graphs represented by adjacency lists as input. Our algorithms make degree and neighbor queries to the input graph and work with a specified fraction of adversarial erasures in adjacency entries. We focus on two computational tasks: testing if a graph is connected or ε-far from connected and estimating the average degree. For testing connectedness, we discover a threshold phenomenon: when the fraction of erasures is less than ε, this property can be tested efficiently (in time independent of the size of the graph); when the fraction of erasures is at least ε, then a number of queries linear in the size of the graph representation is required. Our erasure-resilient algorithm (for the special case with no erasures) is an improvement over the previously known algorithm for connectedness in the standard property testing model and has optimal dependence on the proximity parameter ε. For estimating the average degree, our results provide an "interpolation" between the query complexity for this computational task in the model with no erasures in two different settings: with only degree queries, investigated by Feige (SIAM J. Comput. `06), and with degree queries and neighbor queries, investigated by Goldreich and Ron (Random Struct. Algorithms `08) and Eden et al. (ICALP `17). We conclude with a discussion of our model and open questions raised by our work.
Cite as

Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma. Erasure-Resilient Sublinear-Time Graph Algorithms. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 80:1-80:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{levi_et_al:LIPIcs.ITCS.2021.80,
  author =	{Levi, Amit and Pallavoor, Ramesh Krishnan S. and Raskhodnikova, Sofya and Varma, Nithin},
  title =	{{Erasure-Resilient Sublinear-Time Graph Algorithms}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{80:1--80:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.80},
  URN =		{urn:nbn:de:0030-drops-136192},
  doi =		{10.4230/LIPIcs.ITCS.2021.80},
  annote =	{Keywords: Graph property testing, Computing with incomplete information, Approximating graph parameters}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.9
Hard Properties with (Very) Short PCPPs and Their Applications

Authors: Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Ron D. Rothblum

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
We show that there exist properties that are maximally hard for testing, while still admitting PCPPs with a proof size very close to linear. Specifically, for every fixed ℓ, we construct a property P^(ℓ)⊆ {0,1}^n satisfying the following: Any testing algorithm for P^(ℓ) requires Ω(n) many queries, and yet P^(ℓ) has a constant query PCPP whose proof size is O(n⋅log^(ℓ)n), where log^(ℓ) denotes the ℓ times iterated log function (e.g., log^(2)n = log log n). The best previously known upper bound on the PCPP proof size for a maximally hard to test property was O(n⋅polylog(n)). As an immediate application, we obtain stronger separations between the standard testing model and both the tolerant testing model and the erasure-resilient testing model: for every fixed ℓ, we construct a property that has a constant-query tester, but requires Ω(n/log^(ℓ)(n)) queries for every tolerant or erasure-resilient tester.
Cite as

Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Ron D. Rothblum. Hard Properties with (Very) Short PCPPs and Their Applications. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 9:1-9:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2020.9,
  author =	{Ben-Eliezer, Omri and Fischer, Eldar and Levi, Amit and Rothblum, Ron D.},
  title =	{{Hard Properties with (Very) Short PCPPs and Their Applications}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{9:1--9:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.9},
  URN =		{urn:nbn:de:0030-drops-116949},
  doi =		{10.4230/LIPIcs.ITCS.2020.9},
  annote =	{Keywords: PCPP, Property testing, Tolerant testing, Erasure resilient testing, Randomized encoding, Coding theory}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.52
Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs

Authors: Amit Levi and Erik Waingarten

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
We introduce a new model for testing graph properties which we call the rejection sampling model. We show that testing bipartiteness of n-nodes graphs using rejection sampling queries requires complexity Omega~(n^2). Via reductions from the rejection sampling model, we give three new lower bounds for tolerant testing of Boolean functions of the form f : {0,1}^n -> {0,1}: - Tolerant k-junta testing with non-adaptive queries requires Omega~(k^2) queries. - Tolerant unateness testing requires Omega~(n) queries. - Tolerant unateness testing with non-adaptive queries requires Omega~(n^{3/2}) queries. Given the O~(k^{3/2})-query non-adaptive junta tester of Blais [Eric Blais, 2008], we conclude that non-adaptive tolerant junta testing requires more queries than non-tolerant junta testing. In addition, given the O~(n^{3/4})-query unateness tester of Chen, Waingarten, and Xie [Xi Chen et al., 2017] and the O~(n)-query non-adaptive unateness tester of Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova, and Seshadhri [Roksana Baleshzar et al., 2017], we conclude that tolerant unateness testing requires more queries than non-tolerant unateness testing, in both adaptive and non-adaptive settings. These lower bounds provide the first separation between tolerant and non-tolerant testing for a natural property of Boolean functions.
Cite as

Amit Levi and Erik Waingarten. Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{levi_et_al:LIPIcs.ITCS.2019.52,
  author =	{Levi, Amit and Waingarten, Erik},
  title =	{{Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{52:1--52:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.52},
  URN =		{urn:nbn:de:0030-drops-101452},
  doi =		{10.4230/LIPIcs.ITCS.2019.52},
  annote =	{Keywords: Property Testing, Juntas, Tolerant Testing, Boolean functions}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.17
Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices

Authors: Amit Levi and Yuichi Yoshida

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract
We design a sublinear-time approximation algorithm for quadratic function minimization problems with a better error bound than the previous algorithm by Hayashi and Yoshida (NIPS'16). Our approximation algorithm can be modified to handle the case where the minimization is done over a sphere. The analysis of our algorithms is obtained by combining results from graph limit theory, along with a novel spectral decomposition of matrices. Specifically, we prove that a matrix A can be decomposed into a structured part and a pseudorandom part, where the structured part is a block matrix with a polylogarithmic number of blocks, such that in each block all the entries are the same, and the pseudorandom part has a small spectral norm, achieving better error bound than the existing decomposition theorem of Frieze and Kannan (FOCS'96). As an additional application of the decomposition theorem, we give a sublinear-time approximation algorithm for computing the top singular values of a matrix.
Cite as

Amit Levi and Yuichi Yoshida. Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 17:1-17:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{levi_et_al:LIPIcs.APPROX-RANDOM.2018.17,
  author =	{Levi, Amit and Yoshida, Yuichi},
  title =	{{Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{17:1--17:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.17},
  URN =		{urn:nbn:de:0030-drops-94210},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.17},
  annote =	{Keywords: Qudratic function minimization, Approximation Algorithms, Matrix spectral decomposition, Graph limits}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact